/*
 * @lc app=leetcode.cn id=905 lang=cpp
 *
 * [905] 按奇偶排序数组
 * [21] 调整数组顺序使奇数位于偶数前面,
 * 且保证奇数和奇数，偶数和偶数之间的相对位置不变
 */

// @lc code=start
class Solution {
 public:
  vector<int> sortArrayByParity(int[] nums) {
    // 奇数个数
    int oddCnt = 0;
    for (int x : nums) {
      if (!isEven(x)) {
        oddCnt;
      }
    }
    int[] copy = nums.clone();
    int i = 0, j = oddCnt;  // 数组奇数区 偶数区已经划分好
    for (int num : copy) {
      if (num % 2 == 1) {
        nums[i++] = num;  // 从头开始遍历，奇数放奇数区
      } else {
        nums[j++] = num;  // 从头开始遍历，偶数放偶数区
      }
    }
  }

  bool isEven(int x) { return x % 2 == 0; }
};

class Solution2 {
 public:
  void reOrderArray(vector<int> &array) {
    // 定义双指针 指向数组头和尾
    int left = 0, right = array.size() - 1;
    // 保证左指针 与 右指针不相遇
    while (i <= j) {
      while (left <= right && array[i] % 2 == 1) i++;
      while (left <= right && array[i] % 2 == 0) j--;
      // 左右两指针分别遇到第一个偶数，奇数，交换值以后，双指针指向的子区间又回到了第一次那样，then继续迭代
      if (left < right) swap(array[i], array[j]);
    }
  }
}
// @lc code=end
